package com.liudachu.interview;

public class fbnq {

    //递归，就是在运行的过程中调用自己。

    //1,1,2,3,5,8,13……  斐波那契数列
    public int fibonacci(int n) {
        if (n == 1 || n == 2)
            return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    //递归方式调用计算了很多次，这种代码效率太低。

    //改为非递归方式，减少计算次数

    int fbnq(int n)
    {
        int a = 1;
        int b = 1;
        int c = a;
        while (n > 2)
        {
            c = a + b;//从第三个数开始，斐波那契数等于前两个数的和；
            a = b;//将前一个数给到a，开始下一次求值
            b = c;//将斐波那契数给b，开始下一次求值
            n--;//每求一次，n都要减一
        }
        return c;
    }
}
